package s6_排序算法.sort3_插入排序;

import s6_排序算法.BaseSort;

import java.util.Arrays;

/**
 * @author wisdomelon
 * @date 2020/7/29 0029
 * @project data_study
 * @jdk 1.8
 * 希尔排序
 */
public class ShellSort extends BaseSort {

    /** 分组因子 */
    public static final int CAPACITY = 2;

    public static void main(String[] args) {
        int arr[] = normal();
        System.out.println(Arrays.toString(arr));
        new ShellSort().asc(arr);
        System.out.println(Arrays.toString(arr));
    }


    @Override
    public void asc(int[] arr) {

        System.out.println("ShellSort-------------------------------");
        long s = System.currentTimeMillis();

        int capacity = getCapacity(arr.length);
        System.out.println("ShellSort capacity: " + capacity);
        //method1(arr, capacity);

        method2(arr, capacity);

        long e = System.currentTimeMillis();
        System.out.println("ShellSort: " + (e-s) + "ms");

    }

    /**
     * 获取分组因子
     * @param length
     * @return
     */
    private int getCapacity(int length) {
        return length / 100 < 2 ? CAPACITY : length / 100;
    }

    /**
     * 希尔排序方式1  交换排序
     * @param arr
     * @param capacity
     */
    private void method1(int[] arr, int capacity) {
        // 根据分组因子， 表示一共需要经历多少次分组
        for(int gap = arr.length / capacity; gap > 0; gap /= capacity) {

            // 遍历每次处理的分组数，对每个分组进行插入排序
            for(int i = gap; i < arr.length; i++) {

                // 遍历每个分组中的元素
                for(int j = i - gap; j >= 0; j -= gap) {

                    // 交换
                    if(arr[j] > arr[j + gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

    /**
     * 希尔排序方式1  移位排序
     * @param arr
     * @param capacity
     */
    private void method2(int[] arr, int capacity) {
        // 根据分组因子， 表示一共需要经历多少次分组
        for(int gap = arr.length / capacity; gap > 0; gap /= capacity) {
            // 遍历每次处理的分组数，对每个分组进行插入排序
            for(int i = gap; i < arr.length; i++) {
                // 记录每次分组中的最后一个值
                int res = arr[i];
                // 记录当前索引
                int index = i;
                // 如果当前索引值 不小于分组制定的数值  且  当前索引值 小于 基于分组因子下的前一个索引值，  说明当前索引值是小值
                while(index >= gap && res < arr[index - gap]) {
                    // 则将 基于分组因子下的前一个索引值 替换到当前索引下 相当于元素值后移一位
                    arr[index] = arr[index - gap];
                    // 按照分组因子进行索引减少
                    index -= gap;
                }

                if(index != i) {
                    // 将中间值插入到指定的索引处
                    arr[index] = res;
                }
            }
        }
    }
}
